package a10_动态规划;

/**
 * <p>
 * a52_回文子串复习2
 * </p>
 *
 * @author flyduck
 * @since 2025/3/28
 */
public class a52_回文子串复习2 {
    //dp[i][j]：chars从下标i到下标j是否为回文子串

    //if(chars[i] != chars[j]){
    //  dp[i][j] = false;
    //}else{
    //  if(j - j <= 1){
    //      dp[i][j] = true;
    //  }else if(i == j){
    //      dp[i][j] = dp[i+1][j-1];
    //  }
    //}

    //初始化：刚开始全部初始化成false

    //遍历顺序：
    //来自于左下角
    //从下往上、从左往右
    public int countSubstrings(String s) {
        int result = 0;
        char[] chars = s.toCharArray();

        boolean[][] dp = new boolean[chars.length][chars.length];
        for (int i = chars.length - 1; i >= 0; i--) {
            for (int j = i; j < chars.length; j++) {
                if(chars[i] != chars[j]){
                    dp[i][j] = false;
                }else {
                    if(j - i <= 1){
                        dp[i][j] = true;
                        result++;
                    }else if(dp[i+1][j-1]){
                        dp[i][j] = true;
                        result++;
                    }
                }
            }
        }
        return result;

    }

}
